1. Field of Invention
The field of invention relates generally to network devices and, more specifically but not exclusively, relates to supporting a large Internet Protocol forwarding information base.
2. Background Information
Networks provide the infrastructure for many forms of communication. LANs (Local Area Network), WANs (Wide Area Network), MANs (Metropolitan Area Network), and the Internet are common networks. Packets sent on networks are often handled by various network devices such as bridges, hubs, switches, and routers.
Routers are special-purpose devices used to interconnect networks. A router can interconnect networks that use different technologies and different addressing schemes. Routers typically support multiple communication protocols.
Interconnecting networks may be done by many different communication protocols. The Internet Protocol (IP) is a Layer 3 protocol that contains addressing information for the routing of packets. Each host is assigned an IP address (a.k.a., an Internet address.) Internet Protocol version 4 (IPv4) uses 32-bit addressing, while Internet Protocol version 6 (IPv6) uses 128-bit addressing. When packets are sent across the Internet, the destination address is attached to the packet. HH
A prefix is a portion of a destination address that may be used for IP routing. The prefix may sometimes be expressed in a slash notation. For example, an IPv4 address is usually represented in a dotted decimal notation, for example, 129.52.6.0, where each 8-bit section (an octet) is separated by a decimal. The IPv4 address 129.52.6.0 may have the prefix 129.52/16 meaning the first 16-bits of the IPv4 address are to be used for routing of a packet. The remaining portion of the IPv4 address refers to the destination within a particular network. Usually, this remaining portion refers to a subnet.
Packets traverse the Internet by following a path from their source through routers to their destination. Each router along the path will examine the destination address of the packet. The router will then determine the most efficient way to forward the packet onto its destination. When a router is to forward a packet, it must determine whether it can send the packet directly to its final destination or whether the packet needs to pass through another router. The place the router will forward the packet is often referred to as the next-hop.
Usually, a router maintains tables used to compute the forwarding path of a packet. Routing tables are used to computer optimal routes to the destination and forwarding tables are used to dictate immediate next-hops for the destination. Forwarding tables are updated by routing protocols based on the routing tables. A forwarding table may also be referred to as a Forwarding Information Base (FIB.) When routing or topology changes occur in a network, the IP routing table is updated, and those changes are reflected in the FIB. The FIB maintains next-hop address information based on the information in the IP routing table.
The router uses a next-hop selection process to determine which route from the FIB to use to forward the packet. One method of selection is the Longest Prefix Match (LPM.) In LPM, the router compares the destination address with the route addresses maintained in the FIB. The path with the longest matching prefix is the chosen path.
The FIBs of today's core routers for IPv4 usually maintain 30,000-50,000 prefixes. These large route tables are maintained at Network Access Points such as Metropolitan Area Exchange (MAE) East and MAE West. While large route tables are in the order of 30,000 to 50,000 prefixes, the requirements for the next generation of routers may range from 256,000 to 1 million prefixes. This number of prefixes and their corresponding next-hop entries result in a very large FIB. Current FIB schemes do not provide for efficient storage and manipulation of such a large number of prefixes.